1. Field of the Invention
This invention pertains generally to methods of performing multiplications in electronic systems, and more particularly to a method of determining shift-add combinations using table lookup.
2. Description of Related Art
Numerous applications rely on performing digital multiplication between a multiplicand and a multiplier to produce a product. By way of example, multiplication with some coefficient numbers is necessary when determining compensation for channel conditions or to process incoming data of any kind.
Implementation of multipliers typically requires a substantial amount of hardware, especially if many bits of accuracy are required. For many applications the multiplier comprises a value between 0 and 1 (represented in binary to any desired bit width), in other applications the multiplier can be scaled down into that range by pre-processing with right shifts.
Typically, in attempting to reduce multiplication overhead many have utilized techniques which operate to limit the number of one bits within each coefficient number in preparation for a power of two multiplication. This power of two can then be known as Canonic Sign Digit. The method determines a coefficient which results in the smallest combination of binary “1” bits that can best represent that number. Once this combination is found, the multiplier is static in hardware and does not change. For signal processing applications that encompass changing coefficients, the typical implementation utilizes a dedicated multiplier, which is hardware intensive and as a result costly.
Accordingly, a need exists for a method of performing rapid and low overhead digital multiplications using a form of power of two multiplications driven from tables and a quick decision tree for narrowing coefficients and generating the combinations based on the table.